# 2025.04.01力扣网刷题
# 比较含退格的字符串——栈、双指针、字符串、模拟——简单
# 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
# 注意：如果对空文本输入退格字符，文本继续为空。
# 示例 1：
# 输入：s = "ab#c", t = "ad#c"
# 输出：true
# 解释：s 和 t 都会变成 "ac"。
# 示例 2：
# 输入：s = "ab##", t = "c#d#"
# 输出：true
# 解释：s 和 t 都会变成 ""。
# 示例 3：
# 输入：s = "a#c", t = "b"
# 输出：false
# 解释：s 会变成 "c"，但 t 仍然是 "b"。
# 提示：
# 1 <= s.length, t.length <= 200
# s 和 t 只含有小写字母以及字符 '#'
# 进阶：
# 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
class Solution(object):
    def backspaceCompare1(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def Push(s, stack, top):
            for i in s:
                if i == '#':
                    if top > 0:
                        stack.pop()
                        top -= 1
                else:
                    stack.append(i)
                    top += 1
        stack1 = []
        stack2 = []
        top1, top2 = 0, 0
        Push(s, stack1, top1)
        Push(t, stack2, top2)
        return stack1 == stack2

    def backspaceCompare(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def delete(s, i, del_s):
            while i >= 0 and s[i] == '#':
                del_s += 1
                i -= 1
            while i >= 0 and del_s > 0:
                if s[i] == '#':
                    del_s += 1
                else:
                    del_s -= 1
                i -= 1
            return i, del_s
        i, del_s = len(s) - 1, 0
        j, del_t = len(t) - 1, 0
        while i >= 0 or j >= 0:
            i, del_s = delete(s, i, del_s)
            j, del_t = delete(t, j, del_t)
            if i < 0 and j < 0:
                break
            elif i < 0 or j < 0:
                if i >= 0 and s[i] == '#' or j >= 0 and t[j] == '#':
                    continue
                else:
                    return False
            else:
                if s[i] == '#' or t[j] == '#':
                    continue
                elif s[i] != t[j]:
                    return False
                else:
                    i -= 1
                    j -= 1
        return True